// 分治 快排 数组划分、数组分块
// 使用 3 指针将数组分为 4 块：[0, left], [left + 1, cur], [cur, right - 1], [right, n - 1]
// [0, left] - left 维护的区间
// [left + 1, cur] - cur 维护的区间
// [cur, right - 1] - 待处理的区间
// [right, n - 1] - right 维护的区间
// cur 负责扫描数组
// 快排的核心就是使用 三指针 方法，只是多了找基准元素的一步
// 找基准元素最优秀的方式就是区间内选择区间内的随机元素，时间复杂度可以逼近 O(n * log n)

// 例题 3：
// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//        请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//        你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//        示例 1:
//
//        输入: [3,2,1,5,6,4], k = 2
//        输出: 5
//        示例 2:
//
//        输入: [3,2,3,1,2,4,5,5,6], k = 4
//        输出: 4
//
//        提示：
//
//        1 <= k <= nums.length <= 105
//        -104 <= nums[i] <= 104

// 解题思路：
// 本题使用快速选择算法 - 快速选择算法是基于快排的
// 使用 三指针 数组划分作为快排的核心思想 数组分块：[0, left], [left + 1, right - 1], [right, n - 1]
// 快速选择 - 即找第 k 大元素是落在哪个区间
// 落在 [right, n - 1]，递归继续找第 k 大元素
// 落在 [left + 1, right - 1]，直接返回 key
// 落在 [0, left]，递归找第 k - ((n - 1) - (left + 1) + 1) 大元素

import java.util.Random;

public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return qsort(nums, 0, n - 1, k);
    }
    public int qsort(int[] nums, int start, int end, int k){
        if(start >= end) return nums[start];
        int left = start - 1; int right = end + 1;
        int cur = start;
        Random random = new Random();
        int index = random.nextInt(end - start + 1) + start;
        int key = nums[index];
        while(cur < right){
            if(nums[cur] < key) swap(nums, ++left, cur++);
            else if(nums[cur] == key) cur++;
            else swap(nums, --right, cur);
        }
        if(end - right + 1 >= k) return qsort(nums, right, end, k);
        else if(end - left >= k) return key;
        else return qsort(nums, start, left, k - (end - left));

    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
